package arithmetic_40;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 *
 * @author wxh
 */
public class Solution_11 {

	/**
	 * 解法1：双端队列解法
	 * @param nums
	 * @param k
	 * @return
	 */
	public int[] maxSlidingWindow(int[] nums, int k) {

		// 边界条件的判断
		if (nums == null || nums.length == 0) {
			return new int[0];
		}

		// 双端队列，就是两边都可以插入和删除数据的队列，这里存储的是元素在数组中的下标，不是元素的值
		Deque<Integer> window = new ArrayDeque<>(k);
		int[] result = new int[nums.length - k + 1]; // 保存结果
		int index = 0;
		for (int i = 0; i < nums.length; i++) {

			// 因为是滑动窗口，所以如果窗口里最大元素的索引，小于等于i - k，说明这个元素不应该在存在这个窗口里了
			if (!window.isEmpty() && window.peekFirst() <= i - k) {
				// peekFirst()：表示的是获取队头，函数pollFirst()表示的是移除并获取队头元素
				window.pollFirst();
			}

			// 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口中队列头部元素永远是队列中最大的
			while (!window.isEmpty() && nums[window.peekLast()] <= nums[i]) {
				window.pollLast(); // 移除队头元素的下标
			}
			window.addLast(i);
			if (i + 1 >= k) { // 只要下标大于等于k，则每次都要找最大值出来（i是从0开始的）
				result[index++] = nums[window.peekFirst()]; // 队列第一个元素就是最大值的下标
			}
		}
		return result;
	}

	/**
	 * 解法2：大顶堆
	 */
	public int[] maxSlidingWindow2(int[] nums, int k) {

		// 1、边界条件的判断
		if (nums == null || nums.length == 0) {
			return new int[0];
		}

		// 2、创建一个大顶堆存放窗口元素，此时堆顶元素就是窗口里面的最大值，堆存储的元素是二元数组[值, 索引]
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] pair1, int[] pair2) {
				//如果值不相等，则按值倒序，否则按索引大小排序（保持原来的顺序）
				return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
			}
		});

		// 3、初始时，将数组nums的前k个元素放入优先队列中
		for (int i = 0; i < k; i++) {
			pq.offer(new int[]{nums[i], i}); //存入二元数组[值, 索引]
		}

		// 4、移动窗口
		int length = nums.length;
		int[] result = new int[length - k + 1]; //初始化结果数组长度 ：一共有 n - k + 1个窗口
		result[0] = pq.peek()[0];//先拿出目前堆顶的元素
		for (int i = k; i < length; i++) { //向右移动滑动窗口
			pq.offer(new int[]{nums[i], i}); //加入大顶堆中
			while (pq.peek()[1] <= i - k) { // 因为是滑动窗口，所以如果窗口里最大元素的索引，小于等于i - k，说明这个元素不应该在存在这个窗口里了
				pq.poll();
			}
			result[i - k + 1] = pq.peek()[0]; //此时堆顶元素就是滑动窗口的最大值
		}

		return result;
	}


	public static void main(String[] args) {

		Solution_11 solution_11 = new Solution_11();
		int[] ints = solution_11.maxSlidingWindow2(new int[] {1,3,-1,-3,5,3,6,7}, 3);
		for (int anInt : ints) {
			System.out.println(anInt);
		}

	}

	class Test{

	}

}